
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def addTwoNumbers(l1,l2):   # 两个链表，返回结果链表
    # 先用两个栈保存链表
    # 1->2->3->4
    # 2->3->4
    s1, s2 = [], []
    while l1:
        s1.append(l1.val)
        l1 = l1.next

    while l2:
        s2.append(l2.val)
        l2 = l2.next

    ans = None  # 结果链表
    carry = 0
    while s1 or s2 or carry != 0:
        a = 0 if not s1 else s1.pop()
        b = 0 if not s2 else s2.pop()
        res = a + b + carry
        carry = res // 10
        res = res % 10
        curNode = ListNode(res)
        curNode.next = ans
        ans = curNode
    return ans

# 用递归写，但是感觉复杂得多
class Solution(object):
    def addTwoNumbersWay2(self,l1,l2):   # 两个链表，返回结果链表
        head1 = l1
        head2 = l2
        while l1 and l2:
            l1 = l1.next
            l2 = l2.next

        while l1:   # len(l1) > len(l2)
            curNode = ListNode(0)
            curNode.next = head2
            head2 = curNode
            l1 = l1.next

        while l2:   # len(l2) > len(l1)
            curNode = ListNode(0)
            curNode.next = head1
            head1 = curNode
            l2 = l2.next

        l1 = head1
        l2 = head2  # len(l1) = len(l2)
        carry = self.addTwoNumbers(l1, l2)
        if carry == 1:
            curNode = ListNode(carry)
            curNode.next = l1
            l1 = curNode
        return l1

    def addTwoNumbers(self, l1,l2): # 计算相同长度链表的和,返回进位和指针
        if l1.next == None:
            carry = (l1.val + l2.val) // 10
            l1.val = (l1.val + l2.val) % 10    # 和存在l1中
            return carry

        nextValue = self.addTwoNumbers(l1.next, l2.next) # 返回上一个的进位信息和节点
        carry = (nextValue + l1.val + l2.val) // 10
        # print(l1.val,l2.val,nextValue)
        l1.val = (nextValue + l1.val + l2.val) % 10
        return carry

if __name__ == '__main__':
    l1 = ListNode(7)
    l1.next = ListNode(2)
    l1.next.next = ListNode(4)
    l1.next.next.next = ListNode(3)

    l2 = ListNode(5)
    l2.next = ListNode(6)
    l2.next.next = ListNode(4)

    s = Solution()
    # print(l1.val)
    s.addTwoNumbersWay2(l1, l2)